//简写单词
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            char[] arr = str.toCharArray();
            int len = arr.length;
            StringBuilder ret = new StringBuilder();
            if (Character.isUpperCase(arr[0])) {
                ret.append(arr[0]);
            }
            else {
                ret.append((char)(arr[0]-32));
            }
            for (int i = 1; i < len; i++) {
                if (arr[i] == ' ') {
                    while (i < len && arr[i] == ' ') {
                        i++;
                    }
                    if (i < len && Character.isUpperCase(arr[i])) {
                        ret.append(arr[i]);
                    }
                    else {
                        ret.append((char)(arr[i]-32));
                    }
                }
            }
            System.out.println(ret.toString());
        }
    }
}
//467
class Solution {
    public int findSubstringInWraproundString(String s) {
        int[] arr = new int[26];
        int len = s.length();
        if (len == 1) {
            return 1;
        }
        int[] dp = new int[len];
        dp[0] = 1;
        arr[s.charAt(0)-'a'] = 1;
        int max = 0;
        for (int i = 1; i < len; i++) {
            char c = s.charAt(i);
            if (c == ((char)(s.charAt(i-1)+1)) || (c == 'a' && s.charAt(i-1)=='z')) {
                dp[i] = 1+dp[i-1];
            }
            else {
                dp[i] = 1;
            }
            arr[c-'a'] = Math.max(arr[c-'a'], dp[i]);
        }

        for (int i = 0; i < 26; i++) {
            max += arr[i];
        }
        System.out.println(Arrays.toString(arr));
        return max;
    }
}
//139
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        s = " "+s;
        //创建一个哈希表
        Map<Character, List<String>> map = new HashMap<>();
        for (int i = 0; i < wordDict.size(); i++) {
            String str = wordDict.get(i);
            char c = str.charAt(0);
            if (map.containsKey(c)) {
                map.get(c).add(str);
            }
            else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(c, list);
            }
        }
        int len = s.length();
        boolean[] dp = new boolean[len];
        dp[0] = true;
        for (int i = 1; i < len; i++) {
            for (int j = i; j > 0; j--) {
                boolean is = dp[j-1];
                List<String> strList = map.get(s.charAt(j));
                if (strList == null) {
                    continue;
                }
                for (int k = 0; strList.size() > k; k++) {
                    String str = strList.get(k);
                    if (is && s.substring(j, i+1).equals(str)) {
                        dp[i] = true;
                        break;
                    }
                }
                if (dp[i]) {
                    break;
                }
            }
        }
        return dp[len-1];
    }
}
//优化
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        s = " "+s;
        //创建一个哈希表
        Set<String> set = new HashSet<>(wordDict);
        int len = s.length();
        boolean[] dp = new boolean[len];
        dp[0] = true;
        for (int i = 1; i < len; i++) {
            for (int j = i; j > 0; j--) {
                boolean is = dp[j-1];
                if (is && set.contains(s.substring(j, i+1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len-1];
    }
}


class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> tmp = new ArrayList<>();
        List<List<Integer>> ret = new ArrayList<>();
        fun1(nums, 0, tmp, ret);
        return ret;
    }

    public void fun1(int[] nums, int i, List<Integer> tmp, List<List<Integer>> ret) {
        if (i == nums.length) {
            ret.add(new ArrayList<>(tmp));
            
            return;
        }
        fun1(nums, i+1, tmp, ret);
        tmp.add(nums[i]);
        fun1(nums, i+1, tmp, ret);
        tmp.remove(tmp.size()-1);
    }
}